# -*- coding: utf-8 -*-

# =============================================================================
# 写的太好!!!
# """
# Definition of TreeNode:
# class TreeNode:
#     def __init__(self, val):
#         self.val = val
#         self.left, self.right = None, None
# """
# 
# class Solution:
#     """
#     @param: root: A Tree
#     @return: Level order a list of lists of integer
#     """
#     def levelOrder(self, root):
#         # write your code here
#         if root is None:return []
#         stack = [root]
#         yy=[]
#         #none就出
#         while stack:
#             y=[]
#             #出栈
#             #每一层,
#             for i in range(len(stack)):
#                 current = stack.pop(0)  # 弹出所有值
#                 y.append(current.val)
#                 if current.left:
#                 #入栈
#                     stack.append(current.left)  # 这两步是用树的下一层重新生成stack
#                 if current.right:  
#                     stack.append(current.right)
#             yy.append(y)
#         return yy
# =============================================================================
    
# =============================================================================
# # Definition for a binary tree node.
# # class TreeNode:
# #     def __init__(self, x):
# #         self.val = x
# #         self.left = None
# #         self.right = None
# 
# class Solution:
#     def isSymmetric(self, root):
#         """
#         :type root: TreeNode
#         :rtype: bool
#         """
#         # 思路主要参考leetcode100题，这里将根节点的左右节点假设成两颗独立的树，这样解题跟100就是类似的了,
#         # 区别：递归调用时，因是对称，所以是左树左节点与右树右节点，左树右节点与右树左节点
#         # 先定义，后调用
#         def isSameTree(p,q):
#             if not p and not q:#两二叉树皆为空，递归边界，两者皆为空返回真  
#                 return True  
#             if p and q and p.val==q.val:  
#                 l=isSameTree(p.left,q.right)#，与leetcode100有区别。递归，每次重新从函数入口处进行，每次进行递归边界判断  
#                 r=isSameTree(p.right,q.left)  
#                 return l and r#and操作，需要l与r皆为true时，才返回真。只用最后一次递归边界return值  
#             else:  
#                 return False
#         if not root:
#             return True
#         else:
#             #p=root.left;q=root.right
#             return isSameTree(root.left,root.right)
# 
# =============================================================================
# =============================================================================
# # Definition for a binary tree node.
# # class TreeNode(object):
# #     def __init__(self, x):
# #         self.val = x
# #         self.left = None
# #         self.right = None
# # 写的太好了,膜拜吧
# class Solution(object):
#     
#     def validBST(self,root,small,large):
#         if root==None:
#             return True
#         if small>=root.val or large<=root.val:
#             return False  
#         return self.validBST(root.left,small,root.val) and self.validBST(root.right,root.val,large)
#         
#         
#     def isValidBST(self, root):
#         """
#         :type root: TreeNode
#         :rtype: bool
#         """
#         return self.validBST(root,-2**32,2**32-1)
# =============================================================================
    
# =============================================================================
# # Definition for a binary tree node.
# # class TreeNode:
# #     def __init__(self, x):
# #         self.val = x
# #         self.left = None
# #         self.right = None
# # 蛋疼的链表和树,
# class Solution:
#     def maxDepth(self, root):
#         """
#         :type root: TreeNode
#         :rtype: int
#         """
#         # #递归边界    
#         if not root:
#             return 0
#         else:
#             l=1+self.maxDepth(root.left)   #递归边界叶子节点数量
#             r=1+self.maxDepth(root.right)
#             return max(l,r)         # 返回更大的
# =============================================================================
